# Author    :Dun_Hz
# Time      :2024/7/29 9:46
# 桶排序
import random


def bucket_sort(li,n=100,max_num=10000):
    buckets=[[] for _ in range(n)]
    for val in li:
        i = min(val//100,n-1)       # 表示这个数应该在第i个桶
        buckets[i].append(val)
        for j in range(len(buckets[i])-1,0,-1):
            if buckets[i][j]<buckets[i][j-1]:
                buckets[i][j],buckets[i][j-1]=buckets[i][j-1],buckets[i][j]
            else:
                break
    sorted_li =[]
    for bucket in buckets:
        sorted_li.extend(bucket)
    return sorted_li

if __name__=="__main__":
    li = [random.randint(0,10000) for i in range(100000)]
    print(bucket_sort(li))